// https://leetcode.cn/problems/binary-tree-level-order-traversal/

// 层序遍历是从上到下一排一排的整出数据


import TreeNode from "./TreeNode";

function levelOrder(root: TreeNode | null): number[][] {
    if(!root) return [];
    //定义返回结果
    const result: number[][] = [];
    // 创建队列
    let queue: TreeNode[] = [];
    // 将根节点入队
    queue.push(root);
    // 当队列有长度，一直出队，并将其左右节点入队
    while(queue.length){
        const level: number[] = [];
        let levelSize = queue.length

        // 这里多遍历一层的原因是为了满足其输出的结果为这样的形式,家这一层是因为有的节点左右子节点都有，则需要放在一个数组里面输出
        // [[3],[9,20],[15,7]]
        // 不加这一层的情况下，结果为[[3],[9],[20],[15],[7]]
        for(let i = 0; i < levelSize; i++){
            // 取出队头元素
            const current =  queue.shift()!;
            level.push(current.val);
        
            // 如果这个节点有左节点，入队
            if(current.left){
            queue.push(current.left);
            }
            // 如果这个节点有右节点，入队
            if(current.right){
            queue.push(current.right);
            }
        }
   
       result.push(level);
    }
    return result;
};

export {}